package com.hwk.dynamic.linked;

import com.hwk.dynamic.List;

public class LinkedList<E> implements List<E> {
    /**
     * 容量
     */
    private int size;

    private Node<E> first;

    /**
     * 找不到的返回下标
     */
    private static final int ELEMENT_NOT_FOUND = -1;

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    @Override
    public void add(E element) {
        add(size,element);
    }

    @Override
    public E get(int index) {
        return this.node(index).element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public void add(int index, E element) {
        if(index == 0){
            first = new Node<E>(element, first.next);
        }else {
            Node<E> pre = node(index - 1);
            pre.next = new Node<E>(element, pre.next);
        }
        size++;
    }

    @Override
    public E remove(int index) {
        E rt;
        if(index ==0){
            rt = first.element;
            first = first.next;
        }else {
            Node<E> pre = node(index - 1);
            rt = pre.next.element;
            pre.next = pre.next.next;
        }
        size--;
        return rt;
    }

    @Override
    public int indexOf(E element) {
        Node<E>  node = first;
        int index = ELEMENT_NOT_FOUND;

        for (int i = 0; i < size; i++) {
            if(node.element.equals(element)){
                index = i;
                break;
            }
            node = node.next;
        }
        return index;
    }

    @Override
    public void clear() {
        first = null;
    }

    private static class Node<E>{
        E element;
        Node<E> next;
        public Node(E element,Node<E> next){
            this.element = element;
            this.next = next;
        }
    }

    private void rangeCheck(int index) {
        if (index < 0 || index >= size) {
            outOfBounds(index);
        }
    }

    private void rangeCheckForAdd(int index) {
        if (index < 0 || index > size) {
            outOfBounds(index);
        }
    }

    private void outOfBounds(int index) {
        throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
    }

    /**
     * 返回第index个节点
     * @param index
     * @return
     */
    private Node<E> node(int index){
        rangeCheck(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

}
